#include <iostream>
#include <vector>
using namespace std;

// 第 N 个泰波那契数
// 动态规划
class Solution
{
public:
    int tribonacci(int n)
    {
        if (n == 0 || n == 1)
            return n;
        vector<int> dp(n + 1);
        dp[0] = 0, dp[1] = 1, dp[2] = 1;
        for (int i = 3; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        return dp[n];
    }
};
// 滚动数组
class Solution
{
public:
    int tribonacci(int n)
    {
        if (n == 0)
            return 0;
        if (n == 1 || n == 2)
            return 1;
        int a = 0, b = 1, c = 1, d = 0;
        for (int i = 3; i <= n; i++)
        {
            d = a + b + c;
            a = b, b = c, c = d;
        }
        return d;
    }
};

// 面试题 08.01. 三步问题
class Solution
{
public:
    int waysToStep(int n)
    {
        if (n == 1 || n == 2)
            return n;
        if (n == 3)
            return 4;
        const int MOD = 1e9 + 7;
        vector<int> dp(n + 1);
        dp[1] = 1, dp[2] = 2, dp[3] = 4;
        for (int i = 4; i <= n; i++)
            dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
        return dp[n];
    }
};

// 使用最小花费爬楼梯
class Solution
{
public:
    int minCostClimbingStairs(vector<int> &cost)
    {
        int n = cost.size();
        vector<int> dp(n + 1);
        dp[0] = 0, dp[1] = 0;
        for (int i = 2; i <= n; i++)
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        return dp[n];
    }
};

// 杨辉三角
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> v(n, vector<int>(n, 1));
    for (int y = 0; y < n; y++)
    {
        for (int x = 0; x < y + 1; x++)
        {
            if (y > 1)
            {
                if (x > 0 && x < y)
                    v[x][y] = v[x][y - 1] + v[x - 1][y - 1];
            }
            printf("%5d", v[x][y]);
        }
        cout << endl;
    }
    return 0;
}

// Fibonacci数列
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int a = 0, b = 1, c = 1;
    while (true)
    {
        if (c >= n)
            break;
        a = b;
        b = c;
        c = a + b; // 这几个顺序不能乱，c = a + b最后算
    }
    cout << min((c - n), (n - b)) << endl;
    return 0;
}

// 约瑟夫问题
class Solution
{
public:
    int LastRemaining_Solution(int n, int m)
    {
        int f = 0; // 第一个孩子拿到礼物的就死他自己
        for (int i = 2; i <= n; i++)
            f = (f + m) % i;
        return f;
    }
};

class Solution
{
public:
    int maxSubarraySumCircular(vector<int> &nums)
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);

        int fmax = INT_MIN, gmin = INT_MAX, sum = 0;
        for (int i = 1; i <= n; i++)
        {
            int x = nums[i - 1];
            f[i] = max(x, x + f[i - 1]);
            fmax = max(fmax, f[i]);
            g[i] = min(x, x + g[i - 1]);
            gmin = min(gmin, g[i]);
            sum += x;
        }
        return sum == gmin ? fmax : max(fmax, sum - gmin);
    }
};

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        unordered_map<long, vector<int>> hash;
        for (int i = 0; i < n; i++) hash[nums[i]].push_back(i);
        vector<vector<int>> dp(n, vector<int>(n));
        int ret = 0;
        for (int i = 2; i < n; i++)
        {
            for (int j = 1; j < i; j++)
            {
                long k = (long)2 * nums[j] - nums[i];
                for (int e : hash[k])
                {
                    if (e < j) dp[j][i] += dp[e][j] + 1;
                }
                ret += dp[j][i];
            }
        }
        return ret;
    }
};
    

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> hash;
        hash[nums[0]] = 0;
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int ret = 2;
        for (int i = 1; i < n; i++) // 固定倒数第二个位置
        {
            for (int j = i + 1; j < n; j++) // 枚举最后一个位置
            {
                int a = 2 * nums[i] - nums[j];
                if (hash.count(a))
                    dp[i][j] = dp[hash[a]][i] + 1;
                ret = max(ret, dp[i][j]);
            }
            hash[nums[i]] = i;
        }
        return ret;
    }
};
    
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int ret = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (s[i] == s[j])
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                if (dp[i][j]) ret++;
            }
        }
        return ret;
    }
}; 
    

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int begin = 0, len = 1;
        for (int i = n - 1; i >= 0; i--)
            for (int j = i; j < n; j++)
            {
                if (s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                if (dp[i][j] && j - i + 1 > len) 
                {
                    len = j - i + 1;
                    begin = i;
                }
            }
        return s.substr(begin, len);
    }
}; 
    

class Solution {
public:
    bool checkPartitioning(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; i--)
            for (int j = i; j < n; j++)
                if (s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
        for (int i = 0; i < n - 1; i++)
            for (int j = 0; j < n - 1; j++)
                if (dp[0][i] && dp[i + 1][j] && dp[j + 1][n - 1])
                    return true;
        return false;
    }
};
    

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                if (s1[i - 1] == s2[j - 1])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + s1[i - 1]);
            }
        }
        int sum = 0;
        for (char ch : s1) sum += ch;
        for (char ch : s2) sum += ch;
        return sum - dp[m][n] - dp[m][n];
    }
};
    